斐波那契

//递归法
#include<bits/stdc++.h>
using namespace std;

int fun(int x){
    if(x==0||x==1){
        return x;
    }else{
        return fun(x-1)+fun(x-2);
    }
}

int main(){
    int n;
    while(cin>>n){
        printf("%d\n",fun(n));
    }
    return 0;
}

//递推法
#include<bits/stdc++.h>
using namespace std;

const int MAXN=35;

int fibonacci[MAXN];

void Initial(){
    fibonacci[0]=0;
    fibonacci[1]=1;
    for(int i=2;i<MAXN;++i){
        fibonacci[i]=fibonacci[i-1]+fibonacci[i-2];
    }
    return;
}

int main(){
    int n;
    while(cin>>n){
        Initial();
        printf("%d\n",fibonacci[n]);
    }
    return 0;
}

//矩阵快速幂较复杂
